package com.lzq.leetcode.hoot100;

public class s33 {

    public int search(int[] nums, int target) {
        int len = nums.length;
        int l = 0, r = len - 1;

        /**
         * 总有一边是有序的, 可以舍弃一边
         */
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else if (nums[mid] <= nums[r]) {
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        s33 s33 = new s33();
        System.out.println(s33.search(new int[]{5, 1, 3}, 3));
    }

}
